package LC;

/**
 * https://leetcode.com/problems/reverse-linked-list-ii/description/
 * Reverse a linked list from position m to n. Do it in-place and in one-pass.
 * For example:
 * Given 1->2->3->4->5->NULL, m = 2 and n = 4,
 * return 1->4->3->2->5->NULL.
 * Note:
 * Given m, n satisfy the following condition:
 * 1 ≤ m ≤ n ≤ length of list.
 */
public class LC_092_ReverseLinkedListII_LinkedList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode h = Solution.reverseBetween(head, 2, 4);
        ListNode cur = h;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    static class Solution {
        static ListNode reverseBetween(ListNode head, int m, int n) {
            ListNode lNode;
            ListNode mNode;
            ListNode rNode;
            lNode = head;
            boolean hasL = true;

            if (m == 1) hasL = false;

            n -= m;
            while (--m > 1) head = head.next;

            if (hasL)
                mNode = head.next;
            else
                mNode = head;

            if (mNode == null)
                return lNode;

            ListNode temp;
            temp = mNode;
            while (n-- > 0)
                temp = temp.next;

            rNode = temp.next;
            temp.next = null;
            mNode = reverseList(mNode);

            if (hasL)
                head.next = mNode;
            else
                head = mNode;

            while (mNode.next != null) mNode = mNode.next;

            mNode.next = rNode;
            if (hasL) return lNode;

            return head;
        }

        static ListNode reverseList(ListNode head) {
            ListNode listNode = null;
            while (head != null) {
                ListNode node = new ListNode(head.val);
                if (listNode != null)
                    node.next = listNode;
                listNode = node;
                head = head.next;
            }
            return listNode;
        }
    }
}
